/*
	一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
*/
int* singleNumbers(int* nums, int numsSize, int* returnSize) {
	int ret = 0;
	int x = 0, y = 0;
	
	for (int i = 0; i < numsSize; i++)
	{
		ret ^= nums[i];
	}
	int offset = 0;
	while (((ret >> offset++) & 1) != 1);
	for (int i = 0; i < numsSize; i++)
	{
		if (((nums[i] >> (offset - 1)) & 1) == 0)
			x ^= nums[i];
		else
			y ^= nums[i];
	}
	int* arr = (int*)malloc(sizeof(int) * 2);
	if (arr == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	*returnSize = 2;
	arr[0] = x;
	arr[1] = y;
	return arr;
}


int main()
{
	int arr[] = {2,3,4,2};
	int sz = sizeof(arr) / sizeof(arr[0]);
	int returnSize;
	int * ret = singleNumbers(arr, sz, &returnSize);

	printf("%d %d \n", ret[0], ret[1]);
	free(ret);
	ret = NULL;
	return 0;
}


/*-----------------------------------------------------------------------------------------------*/